package 排序;

import java.util.Arrays;

/**
 * 快排
 */
public class QuickSort {

    public static void main(String[] args) {

        int[] arr = new int[]{5, 10, 20, 7, 9};
//        sort(arr);
//        System.out.println("arr = " + Arrays.toString(arr));

        arr = new int[]{5, 10, 5, 7, 9, 5, 3, 8};
        sort(arr);
        System.out.println("arr = " + Arrays.toString(arr));
    }

    private static void sort(int[] arr) {


        quickSort(arr, 0, arr.length - 1);

    }


    public static void quickSort(int[] arr, int start, int end) {
        if (start >= end) {
            return;
        }

        int v = arr[start];
        int l = start, r = end;
        while (l < r) {
            // 以开头为中位数，必须先从右边开始向左移，先找到比中位数小的数
            // 这样在递归时，才可以使用左指针进行对半分
            while (l < r && arr[r] >= v)
                r--;
            swap(arr, l, r);

            while (l < r && arr[l] <= v)
                l++;
            swap(arr, l, r);
        }

        quickSort(arr, start, l - 1);
        quickSort(arr, l + 1, end);
    }

    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}
